package leetcode.year2021.month10;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class _01_03Permute46 {
  public List<List<Integer>> permute(int[] nums) {
    int n = nums.length;

    List<List<Integer>> result = new ArrayList<>();

    ArrayList<Integer> integers = new ArrayList<>(nums.length);
    for (int num : nums){
      integers.add(num);
    }

    dfs(integers,n,0,result);

    return result;
  }

  private void dfs(ArrayList<Integer> integers, int n, int first, List<List<Integer>> result) {
    if (first == n){
      result.add(new ArrayList<Integer>(integers));
      return;
    }

    for (int i = first; i < n; i++) {
      Collections.swap(integers, first, i);

      dfs(integers,n,first+1,result);

      Collections.swap(integers, i, first);
    }
  }

  /**
   * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
   *
   *  
   *
   * 示例 1：
   *
   * 输入：nums = [1,2,3]
   * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
   * 示例 2：
   *
   * 输入：nums = [0,1]
   * 输出：[[0,1],[1,0]]
   * 示例 3：
   *
   * 输入：nums = [1]
   * 输出：[[1]]
   *  
   *
   * 提示：
   *
   * 1 <= nums.length <= 6
   * -10 <= nums[i] <= 10
   * nums 中的所有整数 互不相同
   *
   */
}
